The advent of the multimedia PC has been one of the key developments in the computer industry in the 1990s. Originally the term multimedia PC was loosely defined to refer to a personal computer with a CD-ROM and audio capabilities. Recently, however, new applications such as video conferencing, video-on-demand, interactive TV, and virtual reality have been proposed. Rather than the mere integration of text, audio and video, the nature of these applications requires the transfer of high volumes of data between multiple users. As a result, it is now widely recognized that for multimedia to reach its full potential it must become a network based technology rather than a limited local resource.
Unfortunately, the real-time nature of multimedia video and audio streams renders existing local area networks ("LANs") unsuitable for these applications. Conventional LAN designs, most of which are based upon shared media architectures such as Ethernet and Token Ring, have no capability to guarantee the bandwidth and quality of service necessary to accommodate multimedia services. As such, these networks cannot efficiently handle high-speed, real-time video and audio data without introducing significant distortions such as delay, echo and lip synchronization problems.
Recently, as the need for an alternative networking technology to accommodate multimedia in the LAN setting has become apparent, researchers have explored the technologies proposed for the Broadband Integrated Digital Services Network ("B-ISDN"). As high bandwidth requirements and bursty data transmission are commonplace in this wide area network, solutions used in B-ISDN may be applicable to the multimedia LAN environment.
Specifically, the B-ISDN standards, promulgated by the International Telegraph and Telephone Consultative Committee ("CCITT"), now reorganized as the Telecommunications Standardization Sector of the International Telecommunication Union ("ITU-T"), define a packet multiplexing and switching technique, referred to as Asynchronous Transfer Mode ("ATM"). This technique is well known in the art and is described in various references. E.g., Martin de Prycker, Asynchronous Transfer Mode: Solution for Broadband ISDN (2nd Ed., Ellis Horwood Ltd, West Sussex, England, 1993).
In ATM, information is carried in packets of fixed size, specified for B-ISDN as 53 bytes (octets), called cells. Cells are statistically multiplexed into a single transmission facility which may carry hundreds of thousands of ATM cells per second originating from a multiplicity of sources and travelling to a multiplicity of destinations.
ATM is a connection-oriented technology. Rather than broadcasting cells onto a shared wire or fiber for all network members to receive, a specific routing path through the network, called a virtual circuit, is set up between two end nodes before any data is transmitted. Cells identified with a particular virtual circuit are only delivered to nodes on that virtual circuit and are guaranteed to arrive in the transmitted order at the destination of the virtual circuit. ATM also defines virtual paths, bundles of virtual circuits traveling together through at least a portion of the network, the use of which can simplify network management.
The internal nodes of an ATM network comprise switching devices capable of handling the high-speed ATM cell streams. These devices perform the functions required to implement a virtual circuit by receiving ATM cells from an input port, analyzing the information in the header of the incoming cells in real-time, and routing them to the appropriate destination port.
To achieve the most efficient network performance, virtual circuits selected at connection set-up time typically should form the shortest path from source to destination through the internal nodes of the network. Of course, to accurately select this path, the topology or layout of the network must be known.
A popular prior art technique for determination of network topology utilizes a process of flooding the network with topology information cells. See, e.g., U.S. Pat. No. 5,390,170, entitled "Method and Apparatus Providing for Bootstrapping of Switches in an ATM Network or the Like" issued to Sawant et al., on Feb. 14, 1995. In systems employing this technique, each switch transmits link state information cells upon each of its outputs. In turn, every switch which receives an input link state information cell retransmits the cell upon its own output links. In such a manner, topology information from all other internal nodes of the network is collected at each internal node. The entire network configuration can be determined at each internal node by analyzing this collected information.
It is readily apparent, however, that physical loops within the ATM network will create undesirable infinite looping of topology information cells within the network. In FIG. 1, for example, which illustrates a simple ATM network, if switch 120-1 issues a topology information cell, the cell would be sent to switches 120-2 and 120-3. Switches 120-2 and 120-3 would then forward the cell upon their outputs, thus sending topology information cells to switches 120-3 and 120-4, and 120-2 and 120-4, respectively. Upon receipt of these new cells, each of these switches 120-2, 120-3 and 120-4 will again forward the cell upon their respective outputs. In this manner, infinite looping of topology information cells occurs.
Of course, infinite looping may be eliminated by requiring that no physical loops exist within the ATM network. Such a solution is practical in a wide area network where the actual end-node devices connected to the network are unknown. However, physical loops are often highly desirable in ATM LANs. Efficiencies may be achieved by connecting devices requiring repeated, high-performance inter-communications within a small physical loop in the network. For example, many multi-media applications require repetitive communication between specific devices. Performance can be enhanced by confining this communication to a short path between such devices, while still providing access to other devices on the network.
Systems have been disclosed which eliminate the possibility of infinite looping of topology information cells despite the presence of physical loops within the network. See, e.g., U.S. Pat. No. 5,345,558 entitled "Topology Independent Broadcast of Cells in an ATM Network or the Like" issued to Opher et al., on Sep. 6, 1994. In these systems, the topology information cells maintain a record of the number of internal nodes they have visited. After this number reaches a certain predetermined limit, the cell is assumed to be looping and is discarded. However, for any sizable network, the predetermined limit must be sufficiently large to avoid discarding non-looping cells. As a result, although cells will not loop infinitely, they may be permitted to loop for a considerable time. These looping cells will still increase network traffic and degrade overall network performance.
Therefore, a need persists for a method for determining the topology of an ATM network which can reliably operate in a network containing physical loops, but yet avoids the undesirable looping of topology information cells.